package org.czl.tree;

import java.util.List;

public class l1301 {
    public static void main(String[] args) {

    }
    public static int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        int[][][] dp = new int[n][n][2];
        dp[n - 1][n - 1][0] = (board.get(n - 1).charAt(n - 1) - '0');
        dp[n - 1][n - 1][1] = 1;
        for(int i = n - 2; i >= 0; i--){
            if(board.get(n - 1).charAt(i) != 'X'){
                dp[n - 1][i][0] = dp[n - 1][i + 1][0] + (board.get(n - 1).charAt(i) - '0');
                dp[n - 1][i][1] = 1;
            }else{
                break;
            }
        }
        for(int i = n - 2; i >= 0; i--){
            if(board.get(i).charAt(n - 1) != 'X'){
                dp[i][n - 1][0] = dp[i + 1][n - 1][0] + (board.get(i).charAt(n - 1) - '0');
                dp[i][n - 1][1] = 1;
            }else{
                break;
            }
        }

        for(int i = n - 2; i >= 0; i--){
            for(int j = n - 2; j >= 0; j--){
                if(board.get(i).charAt(j) != 'X'){
                    int ret = Math.max(Math.max(dp[i + 1][j][0], dp[i][j + 1][0]), dp[i + 1][j + 1][0]);
                    dp[i][j][0] = ret + (board.get(i).charAt(j) - '0');
                    if(ret == dp[i + 1][j][0])dp[i][j][1] += dp[i + 1][j][1];
                    if(ret == dp[i + 1][j + 1][0])dp[i][j][1] += dp[i + 1][j + 1][1];
                    if(ret == dp[i][j + 1][0])dp[i][j][1] += dp[i][j + 1][1];
                }else{
                    dp[i][j][0] = -100;
                    dp[i][j][1] = 0;
                }
            }
        }
        return dp[0][0];

    }
}
